


#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

class Solution
{
    vector<bool> vis;
    vector<int> tmp;
    vector<vector<int>> res;
    set<vector<int>> hash;
public:
    int maxArea1(vector<int>& height)
    {
        int res = 0;
        int n = height.size();

        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                res = max(res, abs(j - i) * min(height[i], height[j]));
            }
        }

        return res;
    }

    int maxArea2(vector<int>& height)
    {
        int res = 0;
        int n = height.size();

        for (int lf = 0, rg = n - 1; lf < rg;)
        {
            int a = height[lf], b = height[rg];

            res = max(res, min(b, a) * (rg - lf));
            if (a < b)
                ++lf;
            else
                --rg;
        }

        return res;
    }

    vector<vector<int>> permuteUnique1(vector<int>& nums)
    {
        int n = nums.size();
        vis.resize(n, false);

        _permuteUnique1(nums);

        return res;
    }

    vector<vector<int>> permuteUnique2(vector<int>& nums)
    {
        int n = nums.size();
        vis.resize(n, false);

        _permuteUnique2(nums);

        return res;
    }

    void _permuteUnique2(vector<int>& nums)
    {
        if (tmp.size() == nums.size())
        {
            if (!hash.count(tmp))
            {
                res.push_back(tmp);
                hash.insert(tmp);
                return;
            }
        }

        for (int i = 0, n = nums.size(); i < n; ++i)
        {
            if (vis[i])
                continue;

            vis[i] = true;
            tmp.push_back(nums[i]);

            _permuteUnique2(nums);

            tmp.pop_back();
            vis[i] = false;
        }
    }

    vector<vector<int>> permuteUnique3(vector<int>& nums)
    {
        int n = nums.size();
        vis.resize(n, false);

        sort(nums.begin(), nums.end());
        _permuteUnique3(nums);

        return res;
    }

    vector<vector<int>> permuteUnique4(vector<int>& nums)
    {
        int n = nums.size();
        vis.resize(n, false);

        sort(nums.begin(), nums.end());
        _permuteUnique4(nums);

        return res;
    }

private:
    void _permuteUnique4(vector<int>& nums)
    {
        for (int i = 0, n = nums.size(); i < n; ++i)
        {
            if ((i > 0 && nums[i - 1] == nums[i] && vis[i - 1]) || vis[i])
                continue;

            vis[i] = true;
            tmp.push_back(nums[i]);

            if (tmp.size() == n)
                res.push_back(tmp);
            else
                _permuteUnique4(nums);

            tmp.pop_back();
            vis[i] = false;
        }
    }

    void _permuteUnique3(vector<int>& nums)
    {
        if (tmp.size() == nums.size())
        {
            res.push_back(tmp);
            return;
        }

        for (int i = 0, n = nums.size(); i < n; ++i)
        {
            if ((i > 0 && nums[i - 1] == nums[i] && vis[i - 1]) || vis[i])
                continue;

            vis[i] = true;
            tmp.push_back(nums[i]);

            _permuteUnique3(nums);

            tmp.pop_back();
            vis[i] = false;
        }
    }

    void _permuteUnique1(vector<int>& nums)
    {
        for (int i = 0, n = nums.size(); i < n; ++i)
        {
            if (vis[i])
                continue;

            vis[i] = true;
            tmp.push_back(nums[i]);
            if (tmp.size() == n)
            {
                if (!hash.count(tmp))
                {
                    res.push_back(tmp);
                    hash.insert(tmp);
                }
            }
            else
            {
                _permuteUnique1(nums);
            }

            tmp.pop_back();
            vis[i] = false;
        }
    }
};

void Test1()
{
    vector<int> v({1, 2, 3});

    Solution().permuteUnique4(v);
}

int main()
{
    Test1();

	return 0;
}